package com.canopys.study.open.test.leetcode;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 21:49 2020/12/20
 * @Modified By:
 */

import java.util.Stack;
import java.util.Vector;

/**
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 * 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "bcabc"
 * 输出："abc"
 * 示例 2：
 *
 * 输入：s = "cbacdcbc"
 * 输出："acdb"
 *  
 *
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 由小写英文字母组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicate-letters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 解题思路
 * 贪心 + 栈
 * 贪心 : 尽可能将 字典序 最小的字母放前面，
 * 栈 : 存在已经放入的字母
 */
public class RemoveDuplicateLetters {

    public static String removeDuplicateLetters(String s) {
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();

        // 每个字母最后出现的位置
        int[] index = new int['z' - 'a' + 1];

        // 每个字母是否放入到了栈中
        boolean[] vis = new boolean['z' - 'a' + 1];

        // 构建每个字母所处的最后位置
        for (int i = 0; i < chars.length; i++) {
            int curChar = chars[i] - 'a';
            if (index[curChar] < i) {
                index[curChar] = i;
            }
        }

        for (int i = 0; i < chars.length; i++) {
            /*if (stack.isEmpty()) {
                stack.push(chars[i]);
                continue;
            }*/

            // 不理解？？？？？
            if (vis[chars[i] - 'a']) {
                continue;
            }

            while (!stack.isEmpty()) {
                Character peekChar = stack.peek();

                // 如果栈顶元素比当前元素大，则后续元素是否还有栈顶元素，有则push栈顶元素
                if (peekChar.compareTo(chars[i]) > 0 && i < index[peekChar - 'a']) {
                    stack.pop();
                    vis[peekChar - 'a'] = false;
                } else {
                    break;
                }
            }


            // 当前元素是否已经在栈中了，不在接push
            if (!vis[chars[i] - 'a']) {
                stack.push(chars[i]);
                vis[chars[i] - 'a'] = true;
            }
        }

        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        String s = "abacb";
        System.out.println(removeDuplicateLetters(s));
    }
}
